package LinkList;

/*
回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1]
输出：true
示例 2：
输入：head = [1,2]
输出：false
作者：LeetCode
链接：https://leetcode.cn/leetbook/read/linked-list/fov6t/
 */

public class _34回文链表 {
    public static void main(String[] args) {

    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    //创建一个翻转链表，然后对比
    //时间复杂度O(n)，空间复杂度O(n)
    public boolean isPalindrome(ListNode head) {
        if(head == null){
            return false;
        }
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null){
            ListNode reveseNode = new ListNode(cur.val, pre);//创建一个新结点，将它连接到前驱结点，以此创建达到翻转链表的目的
            cur = cur.next;
            pre = reveseNode;//循环结束后，pre就是翻转链表的头结点
        }
        cur = head;
        while (cur != null){
            if(cur.val != pre.val){
                return false;
            }
            cur = cur.next;
            pre = pre.next;
        }
        return true;

    }

    //官解：链表数组法
    //时间复杂度O(n)，空间复杂度O(n)

    /*
        public boolean isPalindrome(ListNode head) {
            List<Integer> vals = new ArrayList<Integer>();

            // 将链表的值复制到数组中
            ListNode currentNode = head;
            while (currentNode != null) {
                vals.add(currentNode.val);
                currentNode = currentNode.next;
            }

            // 使用双指针判断是否回文
            int front = 0;
            int back = vals.size() - 1;
            while (front < back) {
                if (!vals.get(front).equals(vals.get(back))) {
                    return false;
                }
                front++;
                back--;
            }
            return true;
        }

     */

    //官解：递归
    //建议看链接里的图解
    //链接：https://leetcode.cn/problems/palindrome-linked-list/solutions/457059/hui-wen-lian-biao-by-leetcode-solution/

    /*
        private ListNode frontPointer;

        private boolean recursivelyCheck(ListNode currentNode) {
            if (currentNode != null) {
                if (!recursivelyCheck(currentNode.next)) {
                    return false;
                }
                if (currentNode.val != frontPointer.val) {
                    return false;
                }
                frontPointer = frontPointer.next;
            }
            return true;
        }

        public boolean isPalindrome(ListNode head) {
            frontPointer = head;
            return recursivelyCheck(head);
        }

     */

    //官解：快慢指针
    //思路:
    //1.找到前半部分链表的尾节点。
    //我们也可以使用快慢指针在一次遍历中找到：慢指针一次走一步，快指针一次走两步，快慢指针同时出发。当快指针移动到链表的末尾时，慢指针恰好到链表的中间。通过慢指针将链表分为两部分。
    //同理可以将这个推广，可将链表分为1/n部分，而不需要提前遍历链表计算长度后，再来切分
    //2.反转后半部分链表。
    //3.判断是否回文。
    //4.恢复链表。
    //5.返回结果。


    /*
        public boolean isPalindrome(ListNode head) {
            if (head == null) {
                return true;
            }

            // 找到前半部分链表的尾节点并反转后半部分链表
            ListNode firstHalfEnd = endOfFirstHalf(head);
            ListNode secondHalfStart = reverseList(firstHalfEnd.next);

            // 判断是否回文
            ListNode p1 = head;
            ListNode p2 = secondHalfStart;
            boolean result = true;
            while (result && p2 != null) {
                if (p1.val != p2.val) {
                    result = false;
                }
                p1 = p1.next;
                p2 = p2.next;
            }

            // 还原链表并返回结果
            firstHalfEnd.next = reverseList(secondHalfStart);
            return result;
        }

        private ListNode reverseList(ListNode head) {
            ListNode prev = null;
            ListNode curr = head;
            while (curr != null) {
                ListNode nextTemp = curr.next;
                curr.next = prev;
                prev = curr;
                curr = nextTemp;
            }
            return prev;
        }

        private ListNode endOfFirstHalf(ListNode head) {
            ListNode fast = head;
            ListNode slow = head;
            while (fast.next != null && fast.next.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            }
            return slow;
        }

     */





}
